/**
 组合总和 ---无限制重复被选取，不限制层数
给定一个**无重复元素**的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以**无限制重复**被选取。
说明：
所有数字（包括 target）都是正整数。解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
输出： [ [7], [2,2,3] ]
示例 2：
输入：candidates = [2,3,5], target = 8,
输出： [ [2,2,2,2], [2,3,3], [3,5] ]
 */
/**
 * 无限制重复被选取？ 没有层数限制
 * 集合来求组合的话，就需要startIndex
 * 【终止】：1. sum>target 2. sum==target
 * !【剪枝】：其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了
 */
var combinationSum = function(candidates, target) {
    let result = [];
    let path = [];
    candidates.sort((a,b)=>a-b); //!为什么需要排序？因为要剪枝，如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了
    const backTracking = (sum, index) => {
      if(sum == target) {
        result.push(path.slice());
        return; 
      }

      for(let i=index; i<candidates.length;i++){
        const n = candidates[i];
        if(sum+n>target) break; //需要canndidates排序
        path.push(n);
        backTracking(sum+n, i); //!index不变，因为可以重复
        path.pop();
      }
    }
    backTracking(0, 0);
    return result;

};
const candidates = [2,3,6,7], target = 7;
console.log('组合总和', combinationSum(candidates, target)); //[ [7], [2,2,3] ]